1. Field of the Invention
This invention relates to decoding. More particularly, this invention relates to decoding using the maximum a Posteriori (MAP) decoding technique. Particularly but not exclusively, the invention is used for decoding turbo encoded signal, and particularly but not exclusively in mobile telecommunication systems.
2. Description of the Related Art
Turbo codes are widely used in challenging communications environments such as mobile telephony because they offer a transmission performance which approaches the Shannon limit in noisy conditions. In turbo coding, two recursive systematic convolutional (RSC) coders are provided in parallel, receiving the same information bits but in different orders.
The output of the turbo coder is the systematic information (the original bit stream) which forms the input to one of the RSC coders, together with the parity outputs of each of the RSC coders. This corresponds essentially to two stochastic processes running on the same input data. At the receiver end, a turbo decoder can operate by independently estimating each of the two processes with a decoder, then refining the estimates by iteratively sharing information between the two decoders. In other words, the output of one decoder can be used as a-priori information by the other decoder.
Each decoder therefore produces a soft output indicating the likelihood that the input bit was a one, referred to as a “log likelihood ratio” (LLR).
Each decoder is arranged to accept the received bit stream (comprising systematic imparity information) together with a-priori information (in the form of an LLR or data derived from it) from the other decoder, and generate an output (which can itself be fed to the other decoder).
The calculations which are performed during each iteration are described in, for example, “Implementation of a 3GSP Turbo Decoder on a Programmable DSP Core”, James G. Harrison, 3DSP Corporation White Paper, presented at the Communications Design Conference, San Jose, Calif., Oct. 2, 2001 (www.3dsp.com/pdf/3dspturbowhitepaper.pdf). Briefly, it is not feasible to implement MAP decoding in real time for most commercially desirable data rates at present. Accordingly, simplifications of the MAP algorithm have been sought.
In one, referred to as log-MAP, the simplification is performed by eliminating the substantial number of exponentiation and multiplication operations required by operating in the logarithm domain, so that multiplications become additions and exponentiation is not required. A problem with the log-MAP process is that it is necessary to compute the log of the sum of exponentials. The Jacobian formula provides the following alternative:log(eδ1+eδ2=max(δ1,δ2)+log(1+e−|δ2−δ1|)  (1)
The first term, the Max (a, b) function, is a single instruction for DSP's (digital signal processors) and is easily performed in any other type of processing device. However, the second term (the correction term) must still be computed. For this, various approaches have been proposed. The simplest approach is to ignore the term altogether. This is referred to as the Max-log-MAP algorithm. It provides a reasonable approximation where (a) is much larger than (b) or vice versa, but leads to errors where they are of similar magnitudes.
The above-mentioned paper by Harrison proposes to use a lookup table of eight entries to approximate the second term. In the paper “Linearly Approximated Log-MAP Algorithms for Turbo Decoding”, Cheng & Ottoson, a linear approximation (i.e. a first order approximation, employing a single coefficient) is used which is stated to be particularly suitable for wide band CDMA (WCDMA).
U.S. Pat. No. 6,760,390 (Desai et al) takes a different approach: instead of using the Jacobian substitution to replace the logarithm with the sum of the exponents of several numbers, it uses an alternative expression comprising a first term consisting of the average of the numbers, followed by a second term which must be computed
This second term, like the one above, involves taking the logarithms of exponents. It is therefore approximated by using a Taylor series (a power series). To make calculation in real time possible, the Taylor series is truncated after a number of terms which, since the exponential function converges slowly, means that it is of limited accuracy.
Although in these three approaches some attempt is made to take account of the second term, there is inevitably some sacrifice of accuracy for computational efficiency to a greater or lesser extent. The present invention is intended to provide an alternative implementation of the log-MAP algorithm with good accuracy which can be implemented in real time. Under some circumstances, it will provide a more accurate decoding than the above approaches.
In another aspect, the present invention is intended to provide an approximation which is straightforward to implement, and scalable. These aspects are defined in the claims.
In a first aspect, the invention provides a log-MAP type decoder in which the correction term is computed by using a Padé approximant or continued fraction. In each case, the operation includes at least one division stage, as will be clear from what follows, and in contradistinction to the above-referenced prior art.
Padé approximants and their relation to continued fractions are discussed in H. Padé, ‘Sur la représentation approchée d'une fonction par des fractions rationnelles’, Annales Scientifiques de l'ENS, 1892, and H. Padé, ‘Mémoire sur les développements en fractions continues de la fonction exponentielle, pouvant servir d'introduction à la théorie des fractions continues algébriques’, Annales Scientifiques de l'ENS, 1899.